package org.example.myleet.p940;

public class Solution {

    private static final int MOD = 1000000007;

    public int distinctSubseqII(String s) {
        int n = s.length();
        int[][] dp = new int[n][26];
        int c = s.charAt(0) - 'a';
        dp[0][c] = 1;
        for (int i = 1; i < n; ++i) {
            c = s.charAt(i) - 'a';
            for (int j = 0; j < 26; ++j) {
                if (c == j) {
                    //当c == j时，即为需要更新个数的位置，先统计26种字母作为结尾的可能数总和
                    for (int k = 0; k < 26; ++k) {
                        dp[i][j] += dp[i - 1][k];
                        dp[i][j] %= MOD;
                    }
                    //除了26种字母作为结尾的可能，空字符串也作为一种可能
                    ++dp[i][j];
                    //获得所有可能性之后，通过叠加字母c形成不重复的新的子串
                } else {
                    //当c != j时，字母作为子串结尾的可能数直接转移到i
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        int res = 0;
        //统计26种字母作为结尾的可能数总和
        for (int j = 0; j < 26; ++j) {
            res += dp[n - 1][j];
            res %= MOD;
        }
        return res;
    }
}
